Distribute candies

Time: O(N); Space: O(N); easy

Given an integer array with even length, where different numbers in this array represent different kinds of candies.

Each number means one candy of the corresponding kind.

You need to distribute these candies equally in number to brother and sister.

Return the maximum number of kinds of candies the sister could gain.

Example 1:

Input: candies = [1,1,2,2,3,3]

Output: 3

Explanation:

  • There are three different kinds of candies (1, 2 and 3), and two candies for each kind.

  • Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.

  • The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]

Output: 2

Explanation:

  • For example, the sister has candies [2,3] and the brother has candies [1,1].

  • The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

  • The length of the given array is in range [2, 10,000], and will be even.

  • The number in given array is in range [-100,000, 100,000].

Hints:

  1. To maximize the number of kinds of candies, we should try to distribute candies such that sister will gain all kinds.

  2. What is the upper limit of the number of kinds of candies sister will gain? Remember candies are to distributed equally.

  3. Which data structure is the most suitable for finding the number of kinds of candies?

  4. Will hashset solves the problem? Inserting all candies kind in the hashset and then checking its size with upper limit.

1. Brute Force [O(N!), O(N)]

Algorithm

The brute force approach is really simple. We can generate all the permutations of the given numsnums array representing the candies and determine the number of unique elements in the first half of the generated array.

In order to determine the number of unique elements in the first half of the array, we put all the required elements in a set and count the number of elements in the set. We count such unique elements in the first half of the generated arrays for all the permutations possible and return the size of the largest set.

2. Better Brute Force [O(N^2, O(1)]

Algorithm

Before looking into the idea behind this approach, firstly we need to observe one point. The maximum no. of unique candies which the girl can obtain could be atmost n/2n/2, where nn refers to the number of candies. Further, in case the number of unique candies are below n/2n/2, to maximize the number of unique candies that the girl will obtain, we’ll assign all the unique candies to the girl. Thus, in such a case, the number of unique candies the girl gets is equal to the total number of unique candies in the given candiescandies array.

Now, let’s look at the idea behind this approach. We need to find the total number of unique candies in the given candiescandies array. One way to find the number of unique candies is to traverse over the given candiescandies array. Whenever we encounter an element, say candies[j], we can mark all the elements which are the same as candies[j] as invalid and increment the count of unique elements by 1.

Thus, we need to do such markings for all the elements of candiescandies array. At the end, countcount gives the required number of unique candies that can be given to the girl. Further, the value to be returned is given by: min(n/2, count). Instead finding the min, we can stop the traversal over the given candiescandies array as soon as the countcount exceeds n/2.

3. Using Sorting [O(NLogN), O(1)]

Algorithm

We can sort the given candiescandies array and find out the elements which are unique by comparing the adjacent elements of the sorted array. For every new element found(which isn’t the same as the previous element), we need to update the countcount. At the end, we can return the required result as min(n/2, count), as discussed in the previous approach.

4. Using Set [O(N), O(N)]

Algorithm

  • Traverse over all the elements of the given candiescandies array and keep on putting the elements in a set.

  • By the property of a set, it will contain only unique elements.

  • At the end, we can count the number of elements in the set, given by, say countcount.

  • The value to be returned will again be given by min(count, N/2), as discussed in previous approaches.

  • Here, N refers to the size of the candiescandies array.

[3]:

class Solution4(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def distributeCandies(self, candies):
        """
        :type candies: List[int]
        :rtype: int
        """
        lookup = set(candies)
        return min(len(lookup), len(candies)//2)

[4]:

s = Solution4()

candies = [1,1,2,2,3,3]
assert s.distributeCandies(candies) == 3

candies = [1,1,2,3]
assert s.distributeCandies(candies) == 2